1. Field of the Invention
The present invention relates generally to techniques for data integrity checking, and more particularly to checksums used for data integrity checking.
2. Description of Related Art
While numerous variants of checksums are commonly used to provide data integrity checks in a wide variety of applications, such as networking, zettabyte file systems, logging, etc., the determination of checksums in an efficient manner is still problematic, because the determination of checksums can become a performance bottleneck. Over time, the determination of checksums has evolved to try and eliminate or at least minimize the performance issues.
Early on in the determination of checksums it was recognized that generally computers exhibit a better performance with integer computations. J. G. Fletcher developed the Fletcher Checksum as an alternative to cyclic redundancy codes (J. Fletcher, “An Arithmetic Checksum for Serial Transmissions”, IEEE Transactions on Communications, vol. COM-30, p. 247, January 1982). The Fletcher checksum is an integer arithmetic checksum that exhibits a reasonable level of error detection, and lends itself to software implementation on non-dedicated processors.
Reducing the overhead of error detection increases transmission efficiency and allows higher data transmission rates. Experimentation suggested that throughput could be significantly affected by the implementation of the error detection algorithm utilized. On one occasion, it was reported that the throughput tripled when the implementation of Fletcher's checksum utilized was changed from an unoptimized version to an optimized version, (A. Nakassis, “Fletcher's Error Detection Algorithm: How to implement it efficiently and avoid the most common pitfalls”, ACM Comp. Commun. Rev., Vol. 18, p. 63, October 1988).
The Fletcher/Alder checksum is determined by calculating two partial checksums S1 and S2 and concatenating the two into an integer. Partial checksum S1 is the sum of the bytes in the string of data while partial checksum S2 is the sum of the individual values of partial checksum S1 for each step i, i.e.,S1i+=bi S2i+=S1i where bi represents the ith byte of data were i ranges from 0 to (N−1) for a data string of N bytes.
Various methods have been used to implement the Fletcher/Alder checksum. However, given that second partial checksum S2i is derived from first partial checksum S1i, implementing the Fletcher/Alder checksum for a single Single Instruction Multiple Data (SIMD) pipeline has been problematic and a source of a performance bottleneck.
However, for processors that support multiple SIMD pipelines architectures, a novel approach was presented in U.S. Pat. No. 5,960,012, entitled “Checksum Determination Using Parallel Computations on Multiple Packed Data Elements” of Lawrence A. Spracklen, Sep. 28, 1999. In this method, the coupling between the two partial checksums of Fletcher/Alder was broken so that each partial checksum could be determined using a SIMD pipeline.
The Fletcher/Alder checksums were represented as:S1n=Σbi S2n=Σ(n−1)bi 
This implementation works well for multiple SIMD pipelines. However, many of the concurrent multiple threading processors support only a single SIMD pipeline, and the performance of SIMD instructions is sub optimal. Further, standard integer implementations of the Fletcher/Alder checksums are not providing sufficient performance and are perceived as a performance bottleneck. Thus, the continued use of the Fletcher/Alder checksum in applications, where performance is an issue, is problematic.